home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / Source / Foundation / Common / ZSimpleAllocator.cpp < prev    next >
Text File  |  1997-07-26  |  13KB  |  512 lines
  1. /*
  2.  *  File:       ZSimpleAllocator.cpp
  3.  *  Summary:    Fast general purpose allocator.
  4.  *  Written by: Jesse Jones
  5.  *
  6.  *  Copyright ｩ 1997 Jesse Jones. 
  7.  *    For conditions of distribution and use, see copyright notice in ZTypes.h  
  8.  *
  9.  *  Change History (most recent first):
  10.  *
  11.  *         <2>     6/20/97    JDJ        Huge block allocation adjusts mHeapSize.
  12.  *         <1>     1/28/97    JDJ        Created
  13.  */
  14.  
  15. #include <ZSimpleAllocator.h>
  16.  
  17. #include <ZDebug.h>
  18. #include <ZExceptions.h>
  19. #include <ZMemUtils.h>
  20. #include <ZUnitTest.h>
  21.  
  22.  
  23. //-----------------------------------
  24. //    Constants
  25. //        On a 601 doubles should be on 8-byte boundaries. On a 604 doubles only need to
  26. //        be on 4-byte boundaries. Since we don't want to give 601 users the shaft and
  27. //        there's no telling what future processors will require we'll align blocks to
  28. //        8-byte boundaries on a PPC.
  29. //
  30. #if powerc
  31. const long kAlignTo = 8;
  32. #else
  33. const long kAlignTo = 4;                // this is fine on 68K's (and NewPtr only aligns to 4-bytes on 68030's)
  34. #endif
  35.  
  36. const long kBlockOverhead = sizeof(long) + sizeof(SPool*);
  37. const long kPoolOverhead  = sizeof(ulong) + 2*sizeof(SPool*) + sizeof(long);
  38.  
  39. const ulong kMaxBlockSize = 0x3FFFFFFFL;    // maximum size for a block in a pool
  40.  
  41.  
  42. // ===================================================================================
  43. //    struct SBlock
  44. // ===================================================================================
  45. struct SBlock {
  46.     unsigned    free : 1;        // set if the block is no longer in use
  47.     unsigned    huge : 1;        // set if the block was allocated with NewPtr (ie not part of a pool)
  48.     unsigned    size : 30;        // size of the entire block (includes header)
  49.     
  50.     SPool*        pool;            // header has to be 8 bytes so we'll remember our pool
  51.  
  52.     Byte        data[8];        // variable length user data
  53. };
  54.  
  55.  
  56. // ===================================================================================
  57. //    struct SPool
  58. // ===================================================================================
  59. struct SPool {
  60.     ulong    marker;                // special tag used for sanity checking
  61.     SPool*    nextPool;
  62.     SPool*    prevPool;
  63.     ulong    size;                // size of the entire pool (includes header)
  64.  
  65.     SBlock    data[1];            // pools start with one block which then gets subdivided
  66. };
  67.  
  68.  
  69. // ===================================================================================
  70. //    Internal Functions
  71. // ===================================================================================
  72.  
  73. //---------------------------------------------------------------
  74. //
  75. // GetPoolEnd
  76. //
  77. //---------------------------------------------------------------
  78. inline SBlock* GetPoolEnd(SPool* pool)
  79. {
  80.     ASSERT(pool != nil);
  81.     
  82.     SBlock* end = reinterpret_cast<SBlock*>((char*) pool + pool->size);
  83.     
  84.     return end;
  85. }
  86.  
  87. //---------------------------------------------------------------
  88. //
  89. // GetNextBlock
  90. //
  91. //---------------------------------------------------------------
  92. inline SBlock* GetNextBlock(SBlock* block)
  93. {
  94.     ASSERT(block != nil);
  95.     ASSERT(!block->huge);        // doesn't make sense to call GetNextBlock on a huge block
  96.     ASSERT(block->size < 16*1024L*1024L);
  97.     
  98.     SBlock* nextBlock = reinterpret_cast<SBlock*>((char*) block + block->size);
  99.     
  100.     return nextBlock;
  101. }
  102.  
  103. #pragma mark -
  104.  
  105. // ===================================================================================
  106. //    class TSimpleAllocator
  107. // ===================================================================================
  108.  
  109. //---------------------------------------------------------------
  110. //
  111. // TSimpleAllocator::~TSimpleAllocator
  112. //
  113. //---------------------------------------------------------------
  114. TSimpleAllocator::~TSimpleAllocator()
  115. {
  116.     SPool* pool = mFirstPool;
  117.     while (pool != nil) {
  118.         SPool* next = pool->nextPool;
  119.         
  120.         DisposePtr((Ptr) pool);
  121.         
  122.         pool = next;
  123.     }
  124. }
  125.  
  126.  
  127. //---------------------------------------------------------------
  128. //
  129. // TSimpleAllocator::TSimpleAllocator
  130. //
  131. //---------------------------------------------------------------
  132. TSimpleAllocator::TSimpleAllocator(ulong initialSize, ulong poolSize, ulong hugeSize)
  133. {
  134.     ASSERT(offsetof(SPool, data) % 16 == 0);            // make sure block start is maximally aligned
  135.     ASSERT(kBlockOverhead % kAlignTo == 0);                // so data is aligned
  136.     ASSERT(sizeof(SBlock) == kBlockOverhead + 8);
  137.     ASSERT(sizeof(SPool) == kPoolOverhead + sizeof(SBlock));
  138.  
  139.     ASSERT(initialSize >= sizeof(SPool));
  140.     ASSERT(poolSize >= sizeof(SPool));
  141.     ASSERT(hugeSize < 16*1024L*1024L);
  142.         
  143.     mFirstPool = nil;                                    // AllocatePool adds the new pool to the head of the list
  144.     
  145.     mNewPoolSize = poolSize;
  146.     mHugeSize    = hugeSize > 0 ? hugeSize : mNewPoolSize/4;
  147.     mHeapSize    = 0;
  148.     mPoolCount   = -1;                    // initial pool doesn't count
  149.  
  150.     mLastSplitBlock = nil;
  151.     mLastEnd        = nil;
  152.     
  153.     mFirstPool = this->AllocatePool(initialSize);
  154.     ThrowIfNil(mFirstPool);
  155. }
  156.  
  157.  
  158. //---------------------------------------------------------------
  159. //
  160. // TSimpleAllocator::Allocate
  161. //
  162. //---------------------------------------------------------------
  163. void* TSimpleAllocator::Allocate(ulong bytes)
  164. {
  165.     SBlock* block = nil;
  166.         
  167.     bytes  = (bytes + kAlignTo - 1) & ~(kAlignTo - 1);
  168.     bytes += kBlockOverhead;
  169.  
  170.     // If it's a huge block try using NewPtr.
  171.     if (bytes >= mHugeSize || bytes > kMaxBlockSize) {
  172.         block = this->AllocateFromHeap(bytes);
  173.         
  174.         if (block != nil)
  175.             mHeapSize += block->size;
  176.     }
  177.     
  178.     // If the bytes isn't too large we can try to allocate it in one
  179.     // of our pools.
  180.     if (bytes <= kMaxBlockSize) {
  181.     
  182.         // If the block we last split is large enough use that.
  183.         if (block == nil && mLastSplitBlock != nil && mLastSplitBlock->size >= bytes)
  184.             block = this->AllocateFromBlock(mLastSplitBlock, mLastEnd, bytes);
  185.         
  186.         // Loop through each pool and try to find a free block that's 
  187.         // large enough.
  188.         if (block == nil)
  189.             for (SPool* pool = mFirstPool; pool != nil && block == nil; pool = pool->nextPool)
  190.                 block = this->AllocateFromPool(pool, bytes);
  191.         
  192.         // Create a new pool.    
  193.         if (block == nil && bytes < mNewPoolSize - kPoolOverhead) {
  194.             SPool* newPool = this->AllocatePool(mNewPoolSize);
  195.             if (newPool != nil) {            
  196.                 block = this->AllocateFromPool(newPool, bytes);
  197.                 ASSERT(block != nil);
  198.             }
  199.         }
  200.         
  201.         // Create a new block of just the right size.
  202.         if (block == nil) {
  203.             block = this->AllocateFromHeap(bytes);
  204.         
  205.             if (block != nil)
  206.                 mHeapSize += block->size;
  207.         }
  208.     }
  209.         
  210.     if (block != nil)
  211.         ASSERT(((long) block->data % kAlignTo) == 0);    // make sure user data is properly aligned
  212.                 
  213.     return block == nil ? nil : block->data;
  214. }
  215.  
  216.  
  217. //---------------------------------------------------------------
  218. //
  219. // TSimpleAllocator::AllocateFromPool
  220. //
  221. //---------------------------------------------------------------
  222. SBlock* TSimpleAllocator::AllocateFromPool(SPool* pool, ulong bytes)
  223. {
  224.     ASSERT(pool != nil);
  225.     ASSERT(pool->marker == 'JESS');
  226.     ASSERT(bytes < 16*1024L*1024L);
  227.  
  228.     SBlock* block = nil;
  229.  
  230.     SBlock* candidate = pool->data;
  231.     SBlock* end = GetPoolEnd(pool);
  232.     
  233.     while (candidate < end && block == nil) {
  234.         if (candidate->free)
  235.             block = this->AllocateFromBlock(candidate, end, bytes);
  236.     
  237.         if (block == nil)
  238.             candidate = GetNextBlock(candidate);
  239.     }
  240.     
  241.     return block;
  242. }
  243.  
  244.  
  245. //---------------------------------------------------------------
  246. //
  247. // TSimpleAllocator::AllocateFromBlock
  248. //
  249. //---------------------------------------------------------------
  250. SBlock* TSimpleAllocator::AllocateFromBlock(SBlock* candidate, const SBlock* end, ulong bytes)
  251. {
  252.     ASSERT(candidate != nil);
  253.     ASSERT(candidate->free);
  254.     ASSERT(!candidate->huge);
  255.     ASSERT(candidate->pool != nil);
  256.     ASSERT(candidate->pool->marker == 'JESS');
  257.     ASSERT(end != nil);
  258.     ASSERT(candidate < end);
  259.     ASSERT(bytes < 16*1024L*1024L);
  260.     
  261.     SBlock* block = nil;
  262.  
  263.     mLastSplitBlock = nil;
  264.     mLastEnd = nil;
  265.     
  266.     // Coalesce all the adjacent freed blocks.
  267.     SBlock* nextBlock = GetNextBlock(candidate);
  268.     while (nextBlock < end && nextBlock->free) {
  269.         candidate->size += nextBlock->size;
  270.     
  271.         nextBlock = GetNextBlock(candidate);
  272.     }
  273.     
  274.     // Use the resulting block or split it in two and use the
  275.     // right part.
  276.     if (candidate->size >= bytes) {
  277.         if (candidate->size >= bytes + sizeof(SBlock)) {
  278.             mLastSplitBlock = candidate;    // remember this block so we can try it next time
  279.             mLastEnd = end;
  280.             
  281.             candidate->size -= bytes;
  282.             
  283.             block = GetNextBlock(candidate);
  284.             block->size = bytes;
  285.         
  286.         } else
  287.             block = candidate;
  288.     }
  289.     
  290.     if (block != nil) {
  291.         block->free = false;
  292.         block->huge = false;
  293.         block->pool = candidate->pool;
  294.     }
  295.         
  296.     return block;
  297. }
  298.  
  299.  
  300. //---------------------------------------------------------------
  301. //
  302. // TSimpleAllocator::AllocateFromHeap
  303. //
  304. //---------------------------------------------------------------
  305. SBlock* TSimpleAllocator::AllocateFromHeap(ulong bytes)
  306. {
  307.     ASSERT(bytes < 16*1024L*1024L);
  308.     
  309.     SBlock* block = reinterpret_cast<SBlock*>(NewPtr(bytes));
  310.     
  311.     if (block != nil) {
  312.         block->free = false;
  313.         block->huge = true;
  314.         block->size = bytes;
  315.         block->pool = nil;
  316.     }
  317.     
  318.     return block;
  319. }
  320.  
  321.  
  322. //---------------------------------------------------------------
  323. //
  324. // TSimpleAllocator::Deallocate
  325. //
  326. //---------------------------------------------------------------
  327. void TSimpleAllocator::Deallocate(void* ptr)
  328. {
  329.     if (ptr != nil) {
  330.         SBlock* block = reinterpret_cast<SBlock*>((char*) ptr - kBlockOverhead);
  331.         
  332.         ASSERT(!block->free);
  333.         ASSERT(((long) block->data % kAlignTo) == 0);
  334.         
  335.         block->free = true;
  336.  
  337.         if (block->huge) {
  338.             ASSERT(block->pool == nil);
  339.             
  340.             mHeapSize -= block->size;
  341.             
  342.             DisposePtr((Ptr) block);
  343.             ASSERT(MemError() == noErr);
  344.  
  345.         } else {
  346.             ASSERT(block->pool != nil);
  347.             ASSERT(block->pool->marker == 'JESS');
  348.         }
  349.     }
  350. }
  351.  
  352.  
  353. //---------------------------------------------------------------
  354. //
  355. // TSimpleAllocator::AllocatePool
  356. //
  357. //---------------------------------------------------------------
  358. SPool* TSimpleAllocator::AllocatePool(ulong size)
  359. {
  360.     SPool* pool = reinterpret_cast<SPool*>(NewPtr(size));
  361.     
  362.     if (pool != nil) {
  363.         pool->marker   = 'JESS';
  364.         pool->nextPool = mFirstPool;
  365.         pool->prevPool = nil;
  366.         pool->size     = size;
  367.         
  368.         if (mFirstPool != nil)
  369.             mFirstPool->prevPool = pool;
  370.         mFirstPool = pool;
  371.  
  372.         pool->data[0].free = true;
  373.         pool->data[0].huge = false;
  374.         pool->data[0].pool = pool;
  375.         pool->data[0].size = size - kPoolOverhead;
  376.         
  377.         mPoolCount++;
  378.         
  379.         mHeapSize += pool->data[0].size;
  380.     }
  381.         
  382.     return pool;
  383. }
  384.  
  385.  
  386. //---------------------------------------------------------------
  387. //
  388. // TSimpleAllocator::GetBlockSize
  389. //
  390. //---------------------------------------------------------------
  391. ulong TSimpleAllocator::GetBlockSize(const void* ptr) const
  392. {
  393.     ASSERT(ptr != nil);
  394.  
  395.     SBlock* block = reinterpret_cast<SBlock*>((char*) ptr - kBlockOverhead);
  396.     ASSERT(!block->free);
  397.     
  398.     ulong bytes = block->size - kBlockOverhead;
  399.     
  400.     return bytes;
  401. }
  402.  
  403.  
  404. //---------------------------------------------------------------
  405. //
  406. // TSimpleAllocator::GetTotalBlockSize
  407. //
  408. //---------------------------------------------------------------
  409. ulong TSimpleAllocator::GetTotalBlockSize(const void* ptr) const
  410. {
  411.     ASSERT(ptr != nil);
  412.  
  413.     SBlock* block = reinterpret_cast<SBlock*>((char*) ptr - kBlockOverhead);
  414.     ASSERT(!block->free);
  415.         
  416.     return block->size;
  417. }
  418.  
  419.  
  420. //---------------------------------------------------------------
  421. //
  422. // TSimpleAllocator::ValidateBlock
  423. //
  424. //---------------------------------------------------------------
  425. #if DEBUG
  426. void TSimpleAllocator::ValidateBlock(const void* ptr) const
  427. {
  428.     ASSERT(ptr != nil);
  429.  
  430.     SBlock* block = reinterpret_cast<SBlock*>((char*) ptr - kBlockOverhead);
  431.     
  432.     ASSERT(!block->free);
  433.     ASSERT(block->size >= sizeof(SBlock));
  434.     ASSERT(((long) block->data % kAlignTo) == 0);
  435.         
  436.     if (block->huge) {
  437.         ASSERT(block->pool == nil);
  438.  
  439.         ulong size = (ulong) GetPtrSize((Ptr) block);
  440.         ASSERT(MemError() == noErr);                // see if the Memory Manager thinks the pointer is valid
  441.         
  442.         if (size <= kMaxBlockSize)
  443.             ASSERT(size == block->size);
  444.             
  445.     } else {
  446.         ASSERT(block->pool != nil);
  447.         ASSERT(block->pool->marker == 'JESS');
  448.     }
  449. }
  450. #endif
  451.  
  452.  
  453. //---------------------------------------------------------------
  454. //
  455. // TSimpleAllocator::ValidateHeap
  456. //
  457. //---------------------------------------------------------------
  458. #if DEBUG
  459. void TSimpleAllocator::ValidateHeap(BlockValidateHook hook, void* refCon) const
  460. {
  461.     for (SPool* pool = mFirstPool; pool != nil; pool = pool->nextPool) {
  462.         ASSERT(pool->marker == 'JESS');
  463.         ASSERT(pool->size >= sizeof(SPool));
  464.  
  465.         SBlock* end = GetPoolEnd(pool);
  466.  
  467.         SBlock* block = pool->data;
  468.         while (block < end) {
  469.             ASSERT(block->pool == pool);
  470.  
  471.             ASSERT(!block->huge);
  472.             ASSERT(((long) block->data % kAlignTo) == 0);
  473.             
  474.             ASSERT(block->size >= sizeof(SBlock));
  475.             ASSERT(block->size < pool->size);
  476.             
  477.             if (!block->free && hook != nil)
  478.                 (*hook)(block->data, (long) (block->size - kBlockOverhead), refCon);
  479.                             
  480.             block = GetNextBlock(block);
  481.         }
  482.     }
  483. }
  484. #endif
  485.  
  486. #pragma mark -
  487.  
  488. // ===================================================================================
  489. //    Unit Test
  490. // ===================================================================================
  491.  
  492. //---------------------------------------------------------------
  493. //
  494. // TestSimpleAllocator
  495. //
  496. // See TAllocator::TestAllocator for allocator comparisons.
  497. //
  498. //---------------------------------------------------------------
  499. #if DEBUG
  500. static void TestSimpleAllocator()
  501. {
  502.     TSimpleAllocator heap1(64*1024L, 32*1024L, 16*1024);
  503.     TSimpleAllocator heap2(64*1024L, 32*1024L, 16*1024);
  504.     TSimpleAllocator heap3(64*1024L, 32*1024L, 16*1024);
  505.  
  506.     TAllocator::TestAllocator(heap1, heap2, heap3);
  507. }
  508.  
  509. static TUnitTestRegistrar sSimpleAllocatorReg("Simple Allocator", TestSimpleAllocator);
  510.  
  511. #endif    // DEBUG
  512.